package com.kobe.algorithm.leetcode.case221;

/**
 * @author ：caopengfei
 * @date ：2021/2/24
 * P(i+n)
 * dp(i,j) = min(dp(i-1,j),dp(i-1,j-1),dp(i,j-1)) +1
 */
public class Solution {


    public int maximalSquare(char[][] matrix) {
        int maxWidth = 0;
        if(matrix == null || matrix.length ==0){
            return  0;
        }
        int [][] intMatrix = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j <matrix[0].length ; j++) {
                if(matrix[i][j] == '1'){
                    int maxWidthTemp;
                    if(  i > 0 && j > 0){
                        maxWidthTemp =  Math.min(Math.min(intMatrix[i-1][j],intMatrix[i-1][j-1]),intMatrix[i][j-1])+1;
                    }else{
                        maxWidthTemp = 1;
                    }
                    intMatrix[i][j] =maxWidthTemp;
                    maxWidth = Math.max(maxWidthTemp,maxWidth);
                }
            }
        }
        return maxWidth*maxWidth;
    }

    private int charToInt(char c){
       return c-'0';
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        char [][]  matrix  = {{'1','1','1','1','0'},{'1','1','1','1','0'},{'1','1','1','1','1'},{'1','1','1','1','1'},{'0','0','1','1','1'}};
        char [][]  matrix2  = {{'0','1'},{'1','0'}};
        System.out.println(solution.maximalSquare(matrix));
    }



}
